2742. Painting the Walls

#Algorithm #Algorithm_Knapsack

2742. Painting the Walls

1. 문제

1-1. 원문

You are given two 0-indexed integer arrays, cost and time, of size n representing the costs and the time taken to paint n different walls respectively. There are two painters available:

Return the minimum amount of money required to paint the n walls.

Example 1:
Input: cost = [1,2,3,2], time = [1,2,3,2]
Output: 3
Explanation: The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.

Example 2:
Input: cost = [2,3,4,2], time = [1,1,1,1]
Output: 4
Explanation: The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.

Constraints:

1-2. 내용 번역

페인트를 칠해야 하는 벽이 N 개 있고, 한명의 유급(페이를 받아야하는) 페인터와 무급(무상 노동하는) 페인터가 있다. 이 때 cost와 time 배열이 주어지는데, cost 배열은 각 벽을 칠할 때 유급 페인터에게 지불해야 하는 액수이고, time 배열은 유급 페인터가 각 벽을 칠할 때 걸리는 시간이다. 그리고 무급 페인터의 경우 하나의 벽을 칠하는데 1시간이 걸린다. 무급 페인터는 유급 페인터가 벽을 칠하는 작업 중에만 일을 할 수 있다. 이 때 모든 벽을 칠하면서 유급 페인터에게 가장 최소로 지불할 수 있는 금액은 얼마인지 리턴해라.

2. 문제 이해

2-1. 내용 이해

Example1을 예로 들어서 문제를 이해해보자.
이 경우에는 4개의 벽이 있는 것을 cost.size or time.size로 알 수 있다. 0번 인덱스의 벽을 유급 페인터가 칠하는 경우 비용은 1을 지불하고 시간이 1시간이 걸리기 때문에 무급 페인터는 다른 벽을 1개 칠 할 수 있게된다. (무급 페인터는 1시간에 1개의 벽을 칠하기 때문.)
유급 페인터와 무급 페인터가 일을 시작한 뒤 1시간 뒤에는 2개의 벽이 칠해져 있고(0번 벽과 다른 벽 하나 더. 무급 페인터는 cost가 비싼 벽을 칠하는게 cost를 줄이는 방법이므로 2번 인덱스 벽을 칠하도록 한다.), 칠해야 하는 벽은 2개가 남는다.
1번 인덱스 벽을 유급 페인터가 칠하게 되면 무급 페인터는 그동안 2개의 벽을 더 칠할 수 있다. (유급 페인터가 칠하고 있는 벽을 제외한 남은 벽이 1개 이기 때문에 충분하다.) 그리고 cost는 2가 더 추가된다.
이렇게 되면 총 비용은 3으로 가장 최소의 비용으로 칠하는 것이 된다.

2-2. 접근법 생각

총 칠해야 하는 벽의 개수를 가방의 무게로, 유급 페인터가 각 벽을 칠하는데 걸리는 시간을 물건의 무게로, 유급 페인터가 각 벽을 칠할 때 받는 금액을 물건의 가치로 치환하여 생각하고, 그 가치가 최소가 되게 한다.

2-3. 적용한 풀이

Knapsack 문제는 풀면 풀 수록 Base Condition을 어떻게 잡느냐가 관건인 것 같다. topdown과 bottomup에 따라서, 물건의 무게 배열을 0번 인덱스부터 시작해서 끝으로 가는지 혹은 그 반대인지에 따라 기초 조건이 달라진다. 그 외에는 DP의 속성인 subproblem으로 나누는 것과 memoization의 배열만 잘 만들어내면 되는 것 같다.

이 문제는 "물건의 무게" 즉 시간을 어떻게 다루는지, 어떤 것으로 변형시키는지가 매우 중요한 문제이다. 벽의 "개수"와 "시간"이 어떻게 연관성을 가지고 연결될 수 있을까?

3. 구현

class Solution {
    val MAX_VALUE = 250000005

    fun paintWalls(cost: IntArray, time: IntArray): Int {
        // return bottomUp(cost, time)
        return topDown(cost, time)
    }

    fun bottomUp(cost: IntArray, time: IntArray): Int {
        val memo: Array<IntArray> = Array(cost.size+1){IntArray(cost.size+1){MAX_VALUE}}
        
        for(i in 0..cost.size) { // 칠해야 하는 벽의 개수가 0개 이면 cost는 0이 든다.
            memo[i][0] = 0
        }

        for (idx in 1..cost.size) {
            for (wallCount in 1..cost.size) {
                val free = memo[idx-1][wallCount]
                val paid = memo[idx-1][Math.max(wallCount-(time[idx-1]+1), 0)] + cost[idx-1]
                memo[idx][wallCount] = Math.min(free, paid)
            }
        }

        return memo[cost.size][cost.size]
    }

    fun topDown(cost: IntArray, time: IntArray): Int {
	    // 배열은 (i-1)번째 인덱스 벽에서의 상황*칠해진 벽의 개수의 의미를 가진다.
        val memo: Array<IntArray> = Array(cost.size+1){IntArray(cost.size+1){-1}}

        for(i in 0..cost.size) {
            memo[i][0] = 0
        }

        return topDownDp(cost, time, memo, 1, cost.size)
    }

    fun topDownDp(cost: IntArray, time: IntArray, memo: Array<IntArray>, curIdx: Int, wallCount: Int): Int {
        if (curIdx > cost.size) { // 마지막 벽의 인덱스를 넘어섰는데, 
            if (wallCount > 0) { // 칠해야 하는 벽의 개수가 1개라도 있으면 모든 벽을 칠했다는 조건에 미달하게 된다.
                return MAX_VALUE
            } else { // 모든 벽을 칠했다면 cost는 0이 된다.
                return 0
            }
        }

        if (wallCount <= 0) { // 칠해야 하는 벽이 하나도 없다면 cost는 0이다.
            return 0
        }

        if (memo[curIdx][wallCount] != -1) {
            return memo[curIdx][wallCount]
        }

		// 해당 벽이 무료로 칠해지는 경우는 지금 벽을 칠한 벽으로 고려하지 않는다. (유급 페인터가 작업하고 있는 벽과 그가 걸리는 시간만을 칠한 벽의 개수에 포함시켜야 한다.)
        val free = topDownDp(cost, time, memo, curIdx+1, wallCount) 

		// 해당 벽이 유급 페인터에 의해 칠해졌다면, 해당 벽과 시간을 합해서 기존 칠해진 벽의 개수에 더한 값이 총 칠해진 벽의 개수가 된다. 
        val paid = topDownDp(cost, time, memo, curIdx+1, wallCount-(time[curIdx-1]+1)) + cost[curIdx-1] 

        memo[curIdx][wallCount] = Math.min(free, paid)

        return memo[curIdx][wallCount]
    }
}

4. 복잡도